const { Dictionay } = require('./13.字典类型')
const { Queue } = require('./03.队列_数组')

class Graph {
  constructor() {
    //   顶点
    this.vertexes = []
    // 边
    this.edges = new Dictionay()
  }
  // 添加点的方法
  addVertex(vertex) {
    this.vertexes.push(vertex)
    this.edges.set(vertex, [])
  }
  addEdge(v1, v2) {
    this.edges.get(v1).push(v2)
    this.edges.get(v2).push(v1)
  }
  toString() {
    let resStr = ''
    this.vertexes.forEach(vertex => {
      resStr += vertex + ' -> '
      resStr += this.edges.get(vertex).join(',') + '\n'
    })
    return resStr
  }
  initializeColor() {
    const colors = {}
    this.vertexes.forEach(vertex => (colors[vertex] = 'white'))
    return colors
  }
  // 广度优先搜索基于对列
  BFS(initVertex, hander) {
    const colors = this.initializeColor()
    // 未访问：white
    // 即将访问：grey
    // 已经访问：black
    const queue = new Queue()
    queue.enqueue(initVertex)
    while (!queue.isEmpty()) {
      // 取出对列中的首节点
      const vNode = queue.dequeue()
      // 取出首节点关联的节点
      const vConnecteds = this.edges.get(vNode)
      // 此时vNode节点已经被访问白色变为灰色
      colors[vNode] = 'grey'
      // 将关联节点加入对列
      vConnecteds.forEach(vConeds => {
        if (colors[vConeds] === 'white') {
          colors[vConeds] = 'grey'
          queue.enqueue(vConeds)
        }
      })
      // 访问顶底
      hander(vNode)
      colors[vNode] = 'black'
    }
  }
  DFS(initVertex, hander) {
    const colors = this.initializeColor()
    this.DFSVisit(initVertex, colors, hander)
  }
  DFSVisit(vNode, colors, hander) {
    colors[vNode] = 'grey'
    hander(vNode)
    const vConnecteds = this.edges.get(vNode)
    vConnecteds.forEach(vCed => {
      if (colors[vCed] === 'white') {
        this.DFSVisit(vCed, colors, hander)
      }
    })
    colors[vNode] = 'black'
  }
}
const grap = new Graph()
const myVertex = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I']
myVertex.forEach(v => grap.addVertex(v))
grap.addEdge('A', 'B')
grap.addEdge('A', 'C')
grap.addEdge('A', 'D')
grap.addEdge('B', 'E')
grap.addEdge('B', 'F')
grap.addEdge('C', 'D')
grap.addEdge('C', 'G')
grap.addEdge('D', 'G')
grap.addEdge('D', 'H')
grap.addEdge('E', 'I')
// console.log(grap.toString())
// console.log(grap.initializeColor())
// grap.BFS(grap.vertexes[0], object => console.log(object))
grap.DFS(grap.vertexes[0], object => console.log(object))
